\input{euler.tex}

\begin{document}

\problem[222]{Sphere Packing}

What is the length of the shortest pipe, of internal radius 50mm, that can fully contain 21 balls of radii 30mm, 31mm, ..., 50mm?

Give your answer in micrometres ($10^{-6}$ m) rounded to the nearest integer.

\solution

Imagine the (straight) pipe to be placed vertically, and stack the balls inside. Since the smallest diameter of the balls is big enough that any ball will touch no more than one other ball, the problem can be turned into a two-dimensional problem of stacking circles in a cylinder.

Let the radius of the pipe be $R$. It is easy to find that when two balls of radius $r_1$ and $r_2$ are stacked next to each other, the vertical distance between their centers is 
\[
l(r_1,r_2) = \sqrt{4R(r_1+r_2)-R}.
\]
Hence, for a sequence of stacking $(r_1,\ldots,r_n)$, the length of the pipe that can fully contain this sequence is
\[
L(r_1,\ldots,r_n) = r_1+r_n + \sum_{i=1}^{n-1} \sqrt{4R(r_i+r_{i+1})-R} .
\]
The objective is to minimize $L$.

The standard method for optimization is to model this as a Traveling Salesman Problem, and run dynamic programming algorithm in $\BigO(n^2 2^n)$ time. However, by running exhaustive search with fewer balls, we identify a pattern in the optimal configuration: place the balls from largest to smallest at alternating ends of the pipe toward the middle.

With this heuristic, we find the optimal sequence as (50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49).

To prove why this sequence is optimal, we probably need to make use of the fact that the function $l(r_1,r_2)$ is concave in $(r_1+r_2)$, and that the radii of the balls are evenly spaced. However, the exact proof is unclear.

\answer

1590933

\complexity

Time complexity: $\BigO(n)$

Space complexity: $\BigO(n)$

\reference

http://en.wikipedia.org/wiki/Travelling\_salesman\_problem

http://en.wikipedia.org/wiki/Convex\_function

\end{document} 